The present invention relates to image processing, and in particular transforming binary images by .+-.90 degrees rotation or by transposing of the X-Y axis.
In image processing, images are represented by pixels which can be displayed on a screen, paper or otherwise. If the pixels are in color or in a gray scale, multiple bits are needed to represent the color or gray scale of each image. For certain applications, however, a single bit can represent a pixel. For example, black and white images can be represented with a zero bit for black and a one bit for white. Alternately, even for color or gray scale, a single bit could be used to activate the ink, with a one indicating ink and a zero indicating no ink, or vice versa.
It is often necessary to transform an image. For example, an image might be rotated either plus or minus 90.degree., or the X and Y axes could be transposed. This would be useful, for instance, in changing the orientation of an image on a screen to a desired orientation as is printed out on paper.
FIGS. 1A and 1B illustrate a positive 90.degree. rotation of an image. As can be seen, an image 10 in FIG. 1A is rotated 90.degree. to the position shown in FIG. 1B. The image extends to a position w on the X-axis and h on the Y-axis. Looking at this on a pixel basis, a particular pixel 12 in the output image of FIG. 1B is at a location i on the X-axis and j on the Y-axis. In FIG. 1A, the same pixel in the input image, prior to the rotation, is at a position i on the Y-axis and h-j on the X-axis. Mathematically, the transformation for the three cases of interest is as follows:
Flip X-Y Axes: img.sub.-- out(i,j)=img.sub.-- in(j,i) PA1 Rotate +90.degree.: img.sub.-- out(i,j)=img.sub.-- in(h-j,i) PA1 Rotate -90.degree.: img.sub.-- out(i,j)=img.sub.-- in(j,w-i)
where img.sub.-- out(i,j) is pixel (i,j) of the output image, img.sub.-- in(p,q) is pixel (p,q) of the input image, h is the height of the input image, and w is the width of the input image.
FIG. 2 illustrates the difficulties with doing this transformation. Typically, image data is arranged in rows, with multiple pixels, each represented by a single bit, stored in bytes or words in a register or at a memory location. For example, a byte 14 consists of 8 bits in a row, representing 8 pixels at the bottom, lower left corner of the image. A vertical column of pixels 16 would consist of the first bit in each of 8 different bytes or words 0-7. The bits in the columns must be selected and transformed into a number of bits in a row to accomplish transformation. For example, for a positive 90.degree. rotation, bits 0-7 of column 16 are rotated to the position of row 18 in a transformed image 20 from an original image 22. Similarly, for a negative 90.degree. rotation, column 16 assumes the position of row 24 in transformed image 20, with the order of the bits being reversed from that of row 18 along the X-axis, as shown. For a transposing of the X-Y axes, column 16 will assume the position shown as row 26 in transformed image 20.
The difficulty with such a process is that data is typically manipulated in byte or word form, and moving around a single bit requires a large number of steps. In addition, the bytes or words are organized by rows, not columns. When handling a large image, with a large number of pixels to be transformed, doing such a transformation can be very tedious and take a significant amount of processing time.
Special purpose graphics boards have been developed with instructions and specialized hardware for doing certain pixel manipulations. In addition, some general purpose microprocessors have recently included graphical execution capabilities, and support a number of graphical instructions. For example, the UltraSPARC.TM. microprocessor of Sun Microsystems, Inc., supports a Visual Instruction Set (VIS) for doing certain graphical manipulations. It would be desirable to have a library routine for performing rotation and X-Y transposing transformations using such graphical instructions in a manner which would minimize processing time.